
//					0,1,2,3
//parent:		0,1,2,3
//size: 		1,1,1,1
class UnionFind {
  constructor(n) { //构造一个大小为n的集合
    this.count = n // 子集的个数
    this.parent = new Array(n) // 每个元素对应的父节点
    this.size = new Array(n)  // size数组记录着每棵树的大小
    for (let i = 0; i < n; i++) {
      this.parent[i] = i; // 自己是自己的parent 父节点指向本省
      this.size[i] = 1; // 子集个数都是1
    }
  }

  union (p, q) { //连通结点p和结点q, p和q都是索引
    let rootP = this.find(p);
    let rootQ = this.find(q); // 找到各自的根节点
    if (rootP === rootQ) return // 如果相同 就不需要合并
    // 元素数量小的接到数量多的下面，这样比较平衡
    if (this.size[rootP] > this.size[rootQ]) { // 比较这两个根节点的子集的元素个数
      // 让元素个数小的连接到元素个数大的后面
      this.parent[rootQ] = rootP; // 让q的父节点等于p
      this.size[rootP] += this.size[rootQ]; // p的元素的个数就是原来子集的+q的
    } else {
      this.parent[rootP] = rootQ; // 否则让p的父节点等于q
      this.size[rootQ] += this.size[rootP]; // q的元素个数等于原来的加上p的
    }
    this.count--; // 子集的数量要--
  }

  isConnected (p, q) { //判断p,q是否连通
    return this.find(p) === this.find(q) // p,q的根相同 就在一个子集
  }

  find (x) { //找到x结点的root
    while (this.parent[x] != x) { // 如果这个元素的parent是自己就退出循环
      // 进行路径压缩
      this.parent[x] = this.parent[this.parent[x]]; // 让当前的父节点 指向这个父节点的父节点
      x = this.parent[x]; // 让当前的等于当前的父节点
    }
    return x; // 找到根节点
  }

  getCount () { //返回子集个数
    return this.count;
  }
}

//					0,1,2,3
//parent:		0,1,2,3
//rank: 		1,1,1,1
//采用rank优化
class UnionFind {
  constructor(n) { //构造一个节点数为n的集合
    this.count = n //并查集总数
    this.parent = new Array(n)
    this.rank = new Array(n)  // rank数组记录着每棵树的重量
    for (let i = 0; i < n; i++) {
      this.parent[i] = i; // 自己是自己的parent
      this.rank[i] = 1;	//每个集合上节点的数量
    }
  }

  union (p, q) { //连通结点p和结点q, p和q都是索引
    let rootP = this.find(p);
    let rootQ = this.find(q);
    if (rootP === rootQ) return
    // 深度小的接在深度大元素下
    if (this.rank[rootP] > this.rank[rootQ]) {
      this.parent[rootQ] = rootP;
    } else if (this.rank[rootP] < this.rank[rootQ]) {
      this.parent[rootP] = rootQ;
    } else {
      this.parent[rootP] = rootQ;
      this.rank[rootQ]++
    }
    this.count--;
  }

  isConnected (p, q) { //判断p,q是否连通
    return this.find(p) === this.find(q)
  }

  find (x) { //找到x结点的root
    while (this.parent[x] != x) {
      // 进行路径压缩
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  getCount () { //返回子集个数
    return this.count;
  }
}